//随机生成数组的函数
function creatArray(length){
    let array = new Array(length)
    for(let i = 0, len = length; i < len; i++){
        array[i] = Math.floor(Math.random()*length)
    }
    return array
}
let myArray = creatArray(10000)

/*
* 插入排序
* 例如一开始选中第二个元素，将第二个元素与之前元素比较，小则交换，否则不动，然后选择第三个元素，与之前两个元素依次比较，小则交换位置，依次循环
* 插入排序有两个循环：
* 1.外层循环将数组元素挨个移动
* 2.内层循环则对外循环中选中的元素及它前面的元素进行比较
* 如果内循环中选中的元素比外循环中选中的元素小，那么数组元素会向左移动，为外循环中的这个元素腾出位置
*
* */

function insertSort(arr){
    let temp,inner
    for(let outer = 1; outer < arr.length; outer++){ //为啥从1开始，因为要和之前的元素比较，从0开始就没有之前元素可以比较了
        temp = arr[outer] //存储临时值
        inner = outer //inner往前与元素比较
        while(inner > 0 && (arr[inner - 1] >= temp)){ //当前面还有元素并且前一个元素比当前元素要小时，交换
            arr[inner] = arr[inner - 1]
            inner--
        }
        //内层while循环结束之后，就剩下最先开始选中的值位置没排序好
        arr[inner] = temp //因为最开始的arr[outer]值存在了temp中，所以最后将其赋给arr[inner]即可
    }
}
console.log(myArray)
console.time(`插入排序的时间`)
insertSort(myArray)
console.timeEnd(`插入排序的时间`)
console.log(myArray)